package com.suanfa.jiaoheng;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class 第8课贪婪算法 {

    public static void main(String[] args) {
        List<Course> courses = 创建课程();
        贪婪算法(courses);
    }


    static class Course implements Comparable{
        // 课程名字
        String name;
        // 课程开始时间(距离当天0点的分钟数)
        Integer startTime;
        // 课程结束时间(距离当天0点的分钟数)
        Integer endTime;

        public Course(String name, Integer startTime, Integer endTime) {
            this.name = name;
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Object o) {
            return this.endTime - ((Course) o).endTime;
        }
    }

    static List<Course> 创建课程(){
        List<Course> courses = new ArrayList<>();
        courses.add(new Course("英语",9*60+30,10*60+30));
        courses.add(new Course("音乐",11*60,12*60));
        courses.add(new Course("美术",9*60,10*60));
        courses.add(new Course("计算机",10*60+30,11*60+30));
        courses.add(new Course("数学",10*60,11*60));
        return courses;
    }

    /**
     * 选择结束最早的课+后一节课的开始时间大于等于前一节课的结束时间
     *
     * @param courses
     */
    static void 贪婪算法(List<Course> courses){
        List<Course> selectedCourses = new ArrayList<>();
        Integer lastCourseEndTime = 0;
        // 对集合按结束时间进行排序
        Collections.sort(courses);
        Iterator<Course> courseIterator = courses.iterator();
        while(courseIterator.hasNext()){
            Course course = courseIterator.next();
            if(course.startTime>=lastCourseEndTime){
                selectedCourses.add(course);
                lastCourseEndTime = course.endTime;
            }
        }
        for (Course selectedCourse : selectedCourses) {
            System.out.println(selectedCourse.name);
        }
    }
}
